package 数组题目.前缀和与差分;

// 矩阵区域和
//https://leetcode.cn/problems/matrix-block-sum/
class 矩阵区域和 {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int n = mat.length + 1;
        int m = mat[0].length + 1;
        int[][] matNums = new int[n][m];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                matNums[i][j] = mat[i - 1][j - 1] + matNums[i - 1][j] + matNums[i][j - 1] - matNums[i - 1][j - 1];
            }
        }
        int[][] res = new int[n - 1][m - 1];
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                int row1 = Math.max(i - k, 0);
                int col1 = Math.max(j - k, 0);
                int row2 = Math.min(i + k, n - 2);
                int col2 = Math.min(j + k, m - 2);
                res[i][j] = matNums[row2 + 1][col2 + 1] - matNums[row2 + 1][col1] - matNums[row1][col2 + 1] + matNums[row1][col1];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        new 矩阵区域和().matrixBlockSum(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, 1);
    }
}
